package leetcodecompetition.D366;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2023-10-08-11:09
 * @Description: 1.0
 */
public class T8028 {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length();
        boolean[] bs = new boolean[n];
        int[][] ls = new int[n][2];
        List<Integer> list = new ArrayList<>();
        int pre = -1;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                bs[i] = true;
                ls[i][0] = pre;
                if (pre != -1) {
                    ls[pre][1] = i;
                }
                pre = i;
                list.add(i);
            }
        }
        ls[pre][1] = -1;
        PriorityQueue<int[]> difs = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pre = -1;
        if (list.size() % 2 != 0) return -1;
        for (int l : list) {
            if (pre == -1) {
                pre = l;
                continue;
            }
            difs.add(new int[]{l - pre, pre, l});
            pre = l;
        }
        int res = 0;
        while (!difs.isEmpty()) {
            int[] dif = difs.poll();
            int d = dif[0], l = dif[1], r = dif[2];
            if (l != -1 && r != -1 && bs[l] && bs[r]) {
                difs.offer(new int[]{ls[r][1] - ls[l][0], ls[l][0], ls[r][1]});
                System.out.println(d+" "+l+" "+r);
                res += Math.min(x,d);
                bs[l]=false;
                bs[r]=false;
            }
        }
        return res;
    }
}
